CONNECTION SCIENCE, 2016VOL. 28, NO. 2, 155–170http://dx.doi.org/10.1080/09540091.2016.1151861Analysis of information gain and Kolmogorov complexity forstructural evaluation of cellular automata configurationsMohammad Ali Javaheri Javid, Tim Blackwell, Robert Zimmer andMohammad Majid al-RifaieDepartment of Computing, Goldsmiths, University of London, London, UKABSTRACTShannon entropy fails to discriminate structurally different patternsin two-dimensional images. We have adapted information gain mea-sure and Kolmogorov complexity to overcome the shortcomings ofentropy as a measure of image structure. The measures are cus-tomised to robustly quantify the complexity of images resultingfrom multi-state cellular automata (CA). Experiments with a two-dimensional multi-state cellular automaton demonstrate that thesemeasures are able to predict some of the structural characteristics,symmetry and orientation of CA generated patterns.ARTICLE HISTORYReceived 25 August 2015Accepted 4 February 2016KEYWORDSComplexity; entropy;information gain;Kolmogorov complexity;computationalaesthetics;cellular automata1. IntroductionCellular automata (CA) were initially developed as a material independent framework tostudy the logic of self-reproducing behaviour of biological systems in the late 1940s by vonNeumann and Ulam (Burks,1970). In the 1960s the idea of using CA as artistic tool emergedfrom the works of Knowlton and Schwartz who produced “Pixillation”, one of the early com-puter generated animations (Knowlton,1964; Schwartz and Schwartz,1992). The “TapestryI”and“Tapestry II”, still frames from “Pixillation” won the first prize of theEighth AnnualComputer Art Contestin 1970. The computer arts of Struycken (1976), Brown (2001), Bed-dard and Dodds (2009) and evolutionary architecture of Frazer (1995) are classical exam-ples of CA-based arts. Moreover, CA have been used for music composition, for example,Xenakis (1992) and Miranda (2001).The popularity of John Conway’s Game of Life (Gardner,1970) drew the attention ofa wider community of researchers and digital artists to the unexplored potential of CAapplications, especially in their capacity to generate complex behaviour from simple rules(Brown,1996, July). This fact has been noted by Wolfram, who himself produced some CAarts in the 1980s, “ even a program that may have extremely simple rules will often be ableto generate pictures that have striking aesthetic qualities-sometimes reminiscent of nature,but often unlike anything ever seen before ” (Wolfram, 2002, p. 11). He further emphasisesthat “ one of the things I’ve been meaning to do is to make a bit more of a serious effort touse CA in some kind of computer art ” (Regis,1988, p. 250).CONTACTMohammad Ali Javaheri Javidm.javaheri@gold.ac.uk© 2016 Taylor & Francis
156M. A. JAVAHERI JAVID ET AL.Although classical one-dimensional CA with binary states can exhibit complexbehaviours, experiments with multi-state two-dimensional (2D) CA reveal a very rich spec-trum of symmetric and asymmetric patterns which are extremely challenging to generateusing conventional mathematical methods (Javaheri Javid and te Boekhorst,2006; JavaheriJavid, al Rifaie, and Zimmer,2014).There have been number of studies on the quantitative (Langton,1986) and qualitativebehaviour (Wolfram,1983,1984,2002) of CA but they are mostly concerned with cate-gorising the rule space and the computational properties of CA. Since CA are one of thegenerative tools in computer art, a means of evaluating the structure of CA generated pat-terns would make a substantial contribution towards further automation of CA art. Therehave been some interesting attempts to develop means of controlling emergence of aes-thetic behaviour in CA (Ashlock and Tsang,2009;Li,1988,1989; Mason,1993; Sims,1992)but with less success. This is due to lack of computational methods of human aestheticperception.This work follows Birkhoff’s tradition in studying mathematical bases of aesthetics, espe-cially the association of aesthetic judgement with the degree of order and complexity of astimulus. Shannon’s information theory provided an objective measure of complexity. It ledto emergence of various informational theories of aesthetics. However entropy fails to takeinto account the spatial characteristics of 2D patterns; these characteristics are fundamen-tal in addressing the aesthetic problem in general and of CA generated configurations inparticular.In this paper, following our earlier works (Javaheri Javid et al.,2014; Javaheri Javid, alRifaie,andZimmer,2015a;JavaheriJavid,Blackwell,Zimmer,andalRifaie,2015b),weexam-ineinformation gainandKolmogorov complexityas measures of complexity in multi-state2D CA generated configurations.This paper is organised as follows. Section2 provides formal definitions and establishesnotations of CA. Section3 demonstrates that entropy is an inadequate measure of discrim-inating multi-state 2D CA configurations. In Section4 the potential of information gainas a structural complexity measure is discussed. Section5 provides formal notions of Kol-mogorov complexity and a method of estimating it. Section6 gives details of experimentsthat test the effectiveness of information gain and its relation to Kolmogorov complexity.The paper closes with a discussion and summary of findings.2. Definition of CADefinition 2.1:A cellular automaton is a regular tiling of a lattice with uniform deterministicfinite state automata.A cellular automatonAis specified by a quadrupleL,S,N,fwhere:Lis a finite square lattice of cells(i,j).S={1, 2,...,k}is set of states. Each cell(i,j)inLhas a statesS.Nis neighbourhood, as specified by a set of lattice vectors{ea},a=1, 2,...,N.Theneighbourhood of cellr=(i,j)is{r+e1,r+e2,...,r+eN}. A a cell is considered to bein its own neighbourhood so that one of{ea}is the zero vector(0, 0). With an economyof notation, the cells in the neighbourhood of(i,j)can be numbered from 1 toN;the